#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

typedef int SLTDataType;
typedef struct SListNode
{
    SLTDataType data;
    struct SListNode* next;
}SListNode;


void SListPrint(SListNode* plist)
{
    SListNode* cur = plist;
    while(cur != nullptr)
    {
        printf("%d-> ", cur->data);
        cur = cur->next;
    }
    printf("NULL\n");
}

SListNode* BuySListNode(SLTDataType x)
{
    SListNode* node = (SListNode*)malloc(sizeof(SListNode));
    if(node == nullptr)
    {
        printf("malloc fail\n");
        exit(-1);
    }
    node->data = x;
    node->next = nullptr;
    return node;
}

void SListPushFront(SListNode** pplist, SLTDataType x)
{
    SListNode* newnode = BuySListNode(x);
    newnode->next = *pplist;
    *pplist = newnode;
}

void SListPushBack(SListNode** pplist, SLTDataType x)
{
    SListNode* newnode = BuySListNode(x);
    if(*pplist == nullptr)
    {
        *pplist = newnode;
    }
    else
    {
        SListNode* tail = *pplist;
        while(tail->next != nullptr)
        {
            tail = tail->next;
        }
        tail->next = newnode;
    }
}

void SListInsertAfter(SListNode* pos, SLTDataType x)
{
    assert(pos);
    SListNode* newnode = BuySListNode(x);
    newnode->next = pos->next;
    pos->next = newnode;
}

void SListInsertBefore(SListNode** pplist, SListNode* pos, SLTDataType x)
{
    assert(pos);
    SListNode* newnode = BuySListNode(x);
    if(pos == *pplist)
    {
        newnode->next = pos;
        *pplist = newnode;
    }
    else
    {
        SListNode* prev = *pplist;
        while(prev->next != pos)
        {
            prev = prev->next;
        }
        newnode->next = prev->next;
        prev->next = newnode;
    }
}

void SListPopFront(SListNode** pplist)
{
    if(*pplist == nullptr)
    {
        return;
    }
    else
    {
        SListNode* tmp = *pplist;
        *pplist = (*pplist)->next;
        free(tmp);
        tmp = nullptr;
    }
}

void SListPopBack(SListNode** pplist)
{
    if(*pplist == nullptr)
    {
        //头结点为空
        return;
    }
    else if((*pplist)->next == nullptr)
    {
        //只要一个结点;
        free(*pplist);
        *pplist = nullptr;
    }
    else
    {
        SListNode* prev = *pplist;
        SListNode* tail = (*pplist)->next;
        while(tail->next != nullptr)
        {
            prev = tail;
            tail = tail->next;
        }
        free(tail);
        tail = nullptr;
        prev->next = nullptr;
    }
}

void SListEraseAfter(SListNode* pos)
{
    assert(pos);
    if(pos->next == nullptr)
    {
        return;
    }
    SListNode* after = pos->next;
    pos->next = after->next;
    free(after);
    after = nullptr;
}

void SListEraseCur(SListNode** pplist, SListNode* pos)
{
    assert(pos);
    if(pos == *pplist)
    {
        *pplist = pos->next;
        free(pos);
        pos = nullptr;
    }
    else
    {
        SListNode* prev = *pplist;
        while(prev->next != pos)
        {
            prev = prev->next;
        }
        prev->next = pos->next;
        free(pos);
        pos = nullptr;
    }
}

SListNode* SListFind(SListNode* plist, SLTDataType x)
{
    SListNode* cur = plist;
    while(cur != nullptr)
    {
        if(cur->data == x)
            return cur;
        cur = cur->next;
    }
    return nullptr;
}

void SListModify(SListNode* pos, SLTDataType x)
{
    pos->data = x;
}


typedef int LTDataType;

typedef struct ListNode
{
    LTDataType data;
    struct ListNode* prev;
    struct ListNode* next;
}ListNode;

ListNode* BuyListNode(LTDataType x)
{
    ListNode* node = (ListNode*)malloc(sizeof(ListNode));
    if(node == nullptr)
    {
        printf("malloc fail!");
        exit(-1);
    }
    node->data = x;
    node->prev = nullptr;
    node->next = nullptr;
}

ListNode* ListInit()
{
    ListNode* phead = BuyListNode(-1);
    phead->prev = phead;
    phead->next = phead;
    return phead;
}

void ListDestory(ListNode* phead)
{
    assert(phead);
    ListNode* cur = phead->next;
    ListNode* next = cur->next;
    while(cur != phead)
    {
        free(cur);
        cur = next;
        next = next->next;
    }
    free(phead);
}

void ListPrint(ListNode* phead)
{
    assert(phead);

    ListNode* cur = phead->next;
    while(cur != phead)
    {
        printf("%d ", cur->data);
        cur = cur->next;
    }
    printf("\n");
}

ListNode* ListFind(ListNode* phead, LTDataType x)
{
    assert(phead);

    ListNode* cur = phead->next;
    while(cur != phead)
    {
        if(cur->data == x)
        {
            return cur;
        }
        cur = cur->next;
    }
    return nullptr;
}

void ListPushFront(ListNode* phead, LTDataType x)
{
    assert(phead);
    ListNode* newnode = BuyListNode(x);
    ListNode* front = phead->next;
    phead->next = newnode;
    newnode->prev = phead;
    newnode->next = front;
    front->next = newnode;
}

void ListPushBack(ListNode* phead, LTDataType x)
{
    assert(phead);
    ListNode* newnode = BuyListNode(x);
    ListNode* tail = phead->prev;
    newnode->next = phead;
    phead->prev = newnode;
    tail->next = newnode;
    newnode->prev = tail;
}

void ListInsert(ListNode* pos, LTDataType x)
{
    assert(pos);
    ListNode* before = pos->prev;
    ListNode* newnode = BuyListNode(x);
    before->next = newnode;
    newnode->prev = before;
    newnode->next = pos;
    pos->prev = newnode;
}

void ListPopFront(ListNode* phead)
{
    assert(phead);
    //这里有哨兵位头结点;
    assert(phead->next != nullptr);

    ListNode* front = phead->next;
    ListNode* newfront = front->next;
    phead->next = newfront;
    newfront->prev = phead;
    free(front);
}

void ListPopBack(ListNode* phead)
{
    assert(phead);
    assert(phead->next != nullptr);
    ListNode* tail = phead->prev;
    ListNode* newtail = tail->prev;
    newtail->next = phead;
    phead->prev = newtail;
    free(tail);
}

void ListErase(ListNode* pos)
{
    assert(pos);
    ListNode* before = pos->prev;
    ListNode* after = pos->next;
    before->next = after;
    after->prev = before;
    free(pos);
}

bool ListEmpty(ListNode* phead)
{
    assert(phead);
    return phead->next == phead;
}

int ListSize(ListNode* phead)
{
    assert(phead);

    int count = 0;
    ListNode* cur = phead;
    while(cur != phead)
    {
        count++;
        cur = cur->next;
    }
    return count;
}